package com.ashin.dp;

import java.util.Arrays;

/**
 * 这里的next数组的含义，表示跳过几个字符，模式匹配的时候模式串的当前字符不匹配，则该不匹配字符外，剩余字符串的最长公共前后缀是多少，排除到自己本省
 *
 * @Author: Ashin
 * @Date: 2020/9/4
 * @Description: com.ashin
 * @Version: 1.0.0
 */
public class KMPExample {


    public static void main(String[] args) {
        String mainString = "ababaaababababbababadab";
        String pattern = "ababa";
        int[] next = next(pattern);

        System.out.println(Arrays.toString(next));

        int patternIdx = 0;
        int mainIdx = 0;
        while (mainIdx < mainString.length()) {
            if (mainString.charAt(mainIdx) == pattern.charAt(patternIdx)) {
                mainIdx++;
                patternIdx++;

            } else if (patternIdx > 0) {
                // 精髓所在 想想next是干什么用的
                int nextIdx = patternIdx - 1;
                patternIdx = next[nextIdx];

            } else {
                mainIdx++;
            }


            if (patternIdx == pattern.length()) {
                // 这里比对完成 直接打印查找的位置
                System.out.println(mainIdx - patternIdx);
                break;
            }
        }
    }

    public static int[] next(String pattern) {
        char[] patterns = pattern.toCharArray();

        // 默认都是0
        int[] next = new int[pattern.length()];

        // 匹配过程中 前后缀最长的值，既是长度，也是next数组下标，前缀指针
        // 这个字段要理解，是精髓，既是长度也是前缀索引下标
        int prefixIdx = 0;
        // 后缀下标字符串第二个开始进行计算，第一个默认是0
        int suffixIdx = 1;
        while (suffixIdx < pattern.length()) {
            // 如果相等
            if (patterns[prefixIdx] == patterns[suffixIdx]) {
                // 长度加1，前缀指针前移（同时也是长度加1）
                prefixIdx++;
                // 记录当前字串截止的最长公共前后缀长度prefixIdx;
                next[suffixIdx] = prefixIdx;
                // 后缀指针前移比较下一个
                suffixIdx++;

                // 这里需要注意，这三句代码的前后顺序不能调换

            } else {
                // 不相等的情况分两种情况
                if (prefixIdx == 0) {
                    // 如果不相等，记录当前字串截止的最长公共前后缀长度prefixIdx;
                    next[suffixIdx] = prefixIdx;
                    // 后缀指针前移下一个
                    suffixIdx++;

                } else {
                    // 如果prefixIdx大于0，即长度不为零，
                    // 精髓所在，好好理解这句代码。
                    // 这句理解了，你就掌握了kmp
                    // 首先想想，如果你不这么写，你会这么写。
                    // 我的理解就是这里把模式串当主串，拿前缀当模式串。有点套娃的意思在里面。
                    // 想想next是干什么用的
                    // 主串和字串进行逐个对比，在遇到不相等的情况。主串指针不变。那子串的指针如何移动。
                    // 就是通过查找next数组来进行移动
                    // 这里是不是遇到不相等的情况了吗
                    // 前缀和后缀的字串patterns[prefixIdx] ！= patterns[suffixIdx]不相等，前缀（模式串）怎么移动
                    // 既prefixIdx怎么移动，不就是通过查找next数组吗？这里有点绕，多体会以下
                    // 前缀prefixIdx指针后退,后退的位置根据已知的next得知
                    // (根据已有的信息，获取下一个prefix的位置和长度,递推思想，根据已有next数组信息推出prefixIdx下一个值)
                    prefixIdx = next[prefixIdx - 1];
                }
            }
        }

        return next;
    }
}
